UnivTrevesV1, LNCS, Analysis, bibRecord, 000206

Polynomial Constants Are Decidable

Identifieur interne : 000206 ( LNCS/Analysis ); précédent : 000205; suivant : 000207

Polynomial Constants Are Decidable

Auteurs : Markus Müller-Olm [Allemagne] ; Helmut Seidl [Allemagne]

Source :

Lecture Notes in Computer Science [ 0302-9743 ] ; 2002.

RBID : ISTEX:B23AF436A3751F520EE989F38508C61937601004

Descripteurs français

Pascal (Inist)
- Constante polynomiale, Décidabilité, Flot donnée, Flot graphe, Graphe fluence, Graphe flux, Non déterminisme, Système non déterministe.

English descriptors

KwdEn :
- Data flow, Decidability, Flow graphs, Fluence graph, Graph flow, Non determinism, Non deterministic system.

Abstract

Abstract: Constant propagation aims at identifying expressions that always yield a unique constant value at run-time. It is well-known that constant propagation is undecidable for programs working on integers even if guards are ignored as in non-deterministic flow graphs. We show that polynomial constants are decidable in non-deterministic flow graphs. In polynomial constant propagation, assignment statements that use the operators +, -,* are interpreted exactly but all assignments that use other operators are conservatively interpreted as non-deterministic assignments. We present a generic algorithm for constant propagation via a symbolic weakest precondition computation and show how this generic algorithm can be instantiated for polynomial constant propagation by exploiting techniques from computable ring theory.

Url:

https://api.istex.fr/document/B23AF436A3751F520EE989F38508C61937601004/fulltext/pdf

DOI: 10.1007/3-540-45789-5_4

Affiliations:

Links to Exploration step

ISTEX:B23AF436A3751F520EE989F38508C61937601004

Le document en format XML

<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Polynomial Constants Are Decidable</title>
<author><name sortKey="Muller Olm, Markus" sort="Muller Olm, Markus" uniqKey="Muller Olm M" first="Markus" last="Müller-Olm">Markus Müller-Olm</name>
</author>
<author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">ISTEX</idno>
<idno type="RBID">ISTEX:B23AF436A3751F520EE989F38508C61937601004</idno>
<date when="2002" year="2002">2002</date>
<idno type="doi">10.1007/3-540-45789-5_4</idno>
<idno type="url">https://api.istex.fr/document/B23AF436A3751F520EE989F38508C61937601004/fulltext/pdf</idno>
<idno type="wicri:Area/Istex/Corpus">001264</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001264</idno>
<idno type="wicri:Area/Istex/Curation">001152</idno>
<idno type="wicri:Area/Istex/Checkpoint">000B46</idno>
<idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000B46</idno>
<idno type="wicri:doubleKey">0302-9743:2002:Muller Olm M:polynomial:constants:are</idno>
<idno type="wicri:Area/Main/Merge">001E86</idno>
<idno type="wicri:source">INIST</idno>
<idno type="RBID">Pascal:03-0334456</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000C40</idno>
<idno type="wicri:Area/PascalFrancis/Curation">000275</idno>
<idno type="wicri:Area/PascalFrancis/Checkpoint">000A81</idno>
<idno type="wicri:explorRef" wicri:stream="PascalFrancis" wicri:step="Checkpoint">000A81</idno>
<idno type="wicri:doubleKey">0302-9743:2002:Muller Olm M:polynomial:constants:are</idno>
<idno type="wicri:Area/Main/Merge">001F46</idno>
<idno type="wicri:Area/Main/Curation">001C37</idno>
<idno type="wicri:Area/Main/Exploration">001C37</idno>
<idno type="wicri:Area/LNCS/Extraction">000206</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Polynomial Constants Are Decidable</title>
<author><name sortKey="Muller Olm, Markus" sort="Muller Olm, Markus" uniqKey="Muller Olm M" first="Markus" last="Müller-Olm">Markus Müller-Olm</name>
<affiliation wicri:level="3"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>University of Dortmund, FB 4, LS5, 44221, Dortmund</wicri:regionArea>
<placeName><region type="land" nuts="1">Rhénanie-du-Nord-Westphalie</region>
<region type="district" nuts="2">District d'Arnsberg</region>
<settlement type="city">Dortmund</settlement>
</placeName>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
<author><name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
<affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country>
<wicri:regionArea>Trier University, FB 4-Informatik, 54286, Trier</wicri:regionArea>
<wicri:noRegion>54286, Trier</wicri:noRegion>
<wicri:noRegion>Trier</wicri:noRegion>
</affiliation>
<affiliation wicri:level="1"><country wicri:rule="url">Allemagne</country>
</affiliation>
</author>
</analytic>
<monogr></monogr>
<series><title level="s">Lecture Notes in Computer Science</title>
<imprint><date>2002</date>
</imprint>
<idno type="ISSN">0302-9743</idno>
<idno type="ISSN">0302-9743</idno>
</series>
<idno type="istex">B23AF436A3751F520EE989F38508C61937601004</idno>
<idno type="DOI">10.1007/3-540-45789-5_4</idno>
<idno type="ChapterID">4</idno>
<idno type="ChapterID">Chap4</idno>
</biblStruct>
</sourceDesc>
<seriesStmt><idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Data flow</term>
<term>Decidability</term>
<term>Flow graphs</term>
<term>Fluence graph</term>
<term>Graph flow</term>
<term>Non determinism</term>
<term>Non deterministic system</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Constante polynomiale</term>
<term>Décidabilité</term>
<term>Flot donnée</term>
<term>Flot graphe</term>
<term>Graphe fluence</term>
<term>Graphe flux</term>
<term>Non déterminisme</term>
<term>Système non déterministe</term>
</keywords>
</textClass>
<langUsage><language ident="en">en</language>
</langUsage>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">Abstract: Constant propagation aims at identifying expressions that always yield a unique constant value at run-time. It is well-known that constant propagation is undecidable for programs working on integers even if guards are ignored as in non-deterministic flow graphs. We show that polynomial constants are decidable in non-deterministic flow graphs. In polynomial constant propagation, assignment statements that use the operators +, -,* are interpreted exactly but all assignments that use other operators are conservatively interpreted as non-deterministic assignments. We present a generic algorithm for constant propagation via a symbolic weakest precondition computation and show how this generic algorithm can be instantiated for polynomial constant propagation by exploiting techniques from computable ring theory.</div>
</front>
</TEI>
<affiliations><list><country><li>Allemagne</li>
</country>
<region><li>District d'Arnsberg</li>
<li>Rhénanie-du-Nord-Westphalie</li>
</region>
<settlement><li>Dortmund</li>
</settlement>
</list>
<tree><country name="Allemagne"><region name="Rhénanie-du-Nord-Westphalie"><name sortKey="Muller Olm, Markus" sort="Muller Olm, Markus" uniqKey="Muller Olm M" first="Markus" last="Müller-Olm">Markus Müller-Olm</name>
</region>
<name sortKey="Muller Olm, Markus" sort="Muller Olm, Markus" uniqKey="Muller Olm M" first="Markus" last="Müller-Olm">Markus Müller-Olm</name>
<name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
<name sortKey="Seidl, Helmut" sort="Seidl, Helmut" uniqKey="Seidl H" first="Helmut" last="Seidl">Helmut Seidl</name>
</country>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/LNCS/Analysis

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000206 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/LNCS/Analysis/biblio.hfd -nk 000206 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    LNCS
   |étape=   Analysis
   |type=    RBID
   |clé=     ISTEX:B23AF436A3751F520EE989F38508C61937601004
   |texte=   Polynomial Constants Are Decidable
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

Serveur d'exploration sur l'Université de Trèves

Polynomial Constants Are Decidable

Polynomial Constants Are Decidable

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

	Serveur d'exploration sur l'Université de Trèves
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.